package com.example.demo.leetcode.top100;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _66搜索旋转排序数组
 * @description
 * @date 2023/06/23 10:29
 * <p>
 * ******************************************************
 */
public class _66搜索旋转排序数组 {

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int num0 = nums[0];
        int first = 0;
        if (nums.length != 1) {

            while (left <= right) {
                int mid = right - (right - left) / 2;
                if (mid > 0) {
                    if (nums[mid] < nums[mid - 1]) {
                        first = mid;
                        break;
                    } else if (nums[mid] > num0) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
        }

        int low;
        int high;
        int finalNum = nums[nums.length - 1];
        if (target > finalNum) {
            low = 0;
            high = (nums.length + first - 1) % nums.length;
        } else {
            low = first;
            high = nums.length - 1;
        }
        while (low <= high) {
            int mid = high - (high - low) / 2;

            if (nums[mid] > target) {
                high = mid - 1;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                return mid;
            }
        }


        return -1;
    }


    public static void main(String[] args) {
        _66搜索旋转排序数组 s = new _66搜索旋转排序数组();
        System.out.println(s.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
    }

}
